package com.devilvan.sort;

import java.util.Arrays;

public class YouGetSort0212 {
    private static YouGetSort youGetSort = new YouGetSort();

    public static void main(String[] args) {
        int[] randoms = youGetSort.getRandoms(100);
//        System.out.println(Arrays.toString(bubbleSort(randoms)));
//        System.out.println(Arrays.toString(quickSort(randoms, 0, randoms.length - 1)));
//        System.out.println(Arrays.toString(insertSort(randoms)));
//        System.out.println(Arrays.toString(selectSort(randoms)));
//        System.out.println(Arrays.toString(shellSort(randoms)));
        System.out.println(Arrays.toString(mergeSort(randoms, 0, randoms.length - 1)));
    }

    // 基数排序
    public static int[] radixSort(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num,max);
        }
        int maxLength = (max + "").length();
        int[][] tempArr = new int[10][nums.length];
        int[] count = new int[10];
        for (int i = 0,n = 1 ; i < maxLength;i++,n*=10) {
            for (int num : nums) {
                int retain = num / n % 10;
                tempArr[retain][count[retain]++] = num;
            }
            int index = 0;
            for (int k = 0;k < count.length;k++) {
                for (int l = 0; l < count[k];l++) {
                    nums[index++] = tempArr[k][l];
                }
                count[k] = 0;
            }
        }
        return nums;
    }

    // 归并排序
    public static int[] mergeSort(int[] nums, int start, int end) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, start, end);
        }
        return nums;
    }

    public static int[] merge(int[] nums, int start, int end) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            int leftIndex = start;
            int rightIndex = mid + 1;
            int[] tempArr = new int[end - start + 1];
            int index = 0;
            while (leftIndex <= mid && rightIndex <= end) {
                tempArr[index++] = nums[leftIndex] <= nums[rightIndex] ? nums[leftIndex++] : nums[rightIndex++];
            }
            while (leftIndex <= mid) {
                tempArr[index++] = nums[leftIndex++];
            }
            while (rightIndex <= end) {
                tempArr[index++] = nums[rightIndex++];
            }
            System.arraycopy(tempArr, 0, nums, start, tempArr.length);
        }
        return nums;
    }


    // 希尔排序
    public static int[] shellSort(int[] nums) {
        for (int d = nums.length; d > 0; d /= 2) {
            for (int i = d; i < nums.length; i++) {
                for (int j = i - d; j >= 0; j -= d) {
                    if (nums[j + d] < nums[j]) {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }
        }
        return nums;
    }

    // 选择排序
    public static int[] selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            int stand = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            nums[i] = nums[minIndex];
            nums[minIndex] = stand;
        }
        return nums;
    }

    // 插入排序
    public static int[] insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int stand = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (stand < nums[j]) {
                    nums[j + 1] = nums[j];
                    nums[j] = stand;
                }
            }
        }
        return nums;
    }

    // 快速排序
    public static int[] quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int stand = nums[start];
            int low = start;
            int high = end;
            while (low < high) {
                while (low < high && nums[high] >= stand) {
                    high--;
                }
                nums[low] = nums[high];
                while (low < high && nums[low] <= stand) {
                    low++;
                }
                nums[high] = nums[low];
            }
            nums[low] = stand;
            quickSort(nums, start, low);
            quickSort(nums, low + 1, end);
        }
        return nums;
    }

    // 冒泡排序
    public static int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j + 1] < nums[j]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }
}
